package com.samxcode.leetcode;

/**
 * Suppose a sorted array is rotated at some pivot unknown to you beforehand.
 * 
 * (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
 * 
 * You are given a target value to search. If found in the array return its index, otherwise return
 * -1.
 * 
 * You may assume no duplicate exists in the array.
 * 
 * Solution: pick the middle item and divide the array into two parts, and we can see there is one
 * side is sorted. Compare the left-most with the middle item, we can check which part is
 * sorted.Then check whether the target belongs to the sorted side, if belong, just search it by the
 * binary search algorithm.Otherwise find it in the unsorted side, the cost of problem reduces by
 * half comparing to the original.
 * 
 * @author Sam
 *
 */
public class SearchInRotatedSortedArray {

    public static void main(String[] args) {
        int[] nums = { 5, 6, 3 };
        System.out.println(search(nums, 3));
    }


    public static int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1, medium;
        while (left <= right) {
            medium = (left + right) / 2;
            if (nums[medium] == target) {
                return medium;
            }
            if (nums[medium] < nums[left]) {
                if (nums[medium] > target || target > nums[right]) {
                    right = --medium;
                } else {
                    return binarySearch(nums, target, medium, right);
                }

            } else {
                if (nums[left] > target || nums[medium] < target) {
                    left = ++medium;
                } else {
                    return binarySearch(nums, target, left, medium);
                }
            }
        }
        return -1;
    }


    private static int binarySearch(int[] nums, int target, int left, int right) {
        int medium;
        while (left <= right) {
            medium = (left + right) / 2;
            if (nums[medium] == target) {
                return medium;
            } else if (nums[medium] > target) {
                right = --medium;
            } else {
                left = ++medium;
            }
        }
        return -1;
    }
}
